package pers.qianyu.month_202101.date_20210108;

/**
 * 198. 打家劫舍
 * https://leetcode-cn.com/problems/house-robber/submissions/
 *
 * @author mizzle rain
 * @date 2021年1月8日23:11:37
 */
public class Rob {
    // 打家劫舍问题双数组思路
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        // f[i] 表示不选 nums[i-1] 时候的最大值
        int[] f = new int[len + 1];
        // g[i] 表示选 nums[i-1] 时候的最大值
        int[] g = new int[len + 1];
        for (int i = 1; i <= nums.length; i++) {
            f[i] = Math.max(f[i - 1], g[i - 1]);
            g[i] = f[i - 1] + nums[i - 1];
        }
        return Math.max(f[len], g[len]);
    }
}